1. Field
The present invention generally relates to rendering two-dimension representations from three-dimensional scenes, and more particularly to using ray tracing for accelerated rendering of photo-realistic two-dimensional representations of scenes.
2. Description of Related Art
Rendering photo-realistic images with ray tracing is well-known in the computer graphics arts. Ray tracing is known to produce photo-realistic images, including realistic shadow and lighting effects, because ray tracing models the physical behavior of light interacting with elements of a scene. However, ray tracing is also known to be computationally intensive, and at present, even a state of the art graphics workstation requires a substantial amount of time to render a complicated scene using ray tracing.
Ray tracing usually involves obtaining a scene description composed of geometric primitives, such as triangles, that describe surfaces of structures in the scene, and modeling how light interacts with primitives in the scene by tracing light rays in the scene. A ray is a vector of virtual light with an origin and a direction in 3-space.
For example, a scene may comprise a car on a street with buildings on either side of the street. The car in such a scene may be defined by a large number of triangles (e.g., 1 million triangles) that approximate a continuous surface. A camera position from which the scene is viewed is defined. A ray cast from the camera is often termed a primary ray, while a ray cast from one object to another, for example, to enable reflection is often called a secondary ray. An image plane of a selected resolution (e.g., 1024×768 for an SVGA display) is disposed at a selected position between the camera and the scene.
A principal objective of ray tracing is to determine a color and intensity for each pixel of the image plane, such that this image can thereafter be displayed on a monitor, for example. In the physical world, viewing such a scene from the camera's perspective would result in light rays reaching the camera that owe their existence to one or more light sources, including diffuse and directed light sources. In the physical world, these light sources project light energy into the scene, and this light energy is transmitted, diffracted, reflected, and/or absorbed according to the types of materials that the light contacts, and the order in which they are contacted, during its journey from light source to the camera. This process is what ray tracing attempts to duplicate.
Although the physical world operates by light energy being traced from a source to the camera, because only a small portion of the light generated by a source arrives at the camera, it has been recognized that rays, for most circumstances, should be traced from the camera back to determine intersections with light sources, instead.
A simplistic ray tracing algorithm involves casting one or more rays from the camera through each pixel of the image into the scene. Each ray is then tested against each primitive composing the scene to identify a primitive which that ray intersects, then it is determined what effect that primitive has on the ray, for example reflecting and/or refracting it. Such reflection and/or refraction causes the ray to proceed in a different direction, and/or split into multiple secondary rays, which can take different paths. All of these secondary rays are then tested against the scene primitives to determine primitives they intersect, and the process recursively continues until the secondary (and tertiary, etc.) ray terminates by, for example, leaving the scene, or hitting a light source. While all of these ray/primitive intersections are being determined, a tree mapping them is created. After a ray terminates, the contribution of the light source is traced back through the tree to determine its effect on the pixel of the scene.
As can be readily understood, the computational complexity of testing 1024×768 (for example) rays for intersection with millions of triangles is computationally expensive—and such ray numbers do not even account for all of the additional rays spawned as a result of material interaction with intersecting rays). Since a ray traverses a scene in a straight line, it has been understood that the “brute force” testing of each ray against each primitive is costly, and by testing a ray first against sub-portions of the primitives, a group of fewer primitives can be identified to test for intersection. Many ways to provide these sub-portions have been proposed and generally are referred to as acceleration structures.
Implicit in the above overview is that each primitive, and acceleration structure has a defined position and extent in the scene. Each ray also must have a specified origin, and a direction. Generally, more accuracy in specifying these items is thought to provide a better ray tracing result, in that more accuracy can allow for greater precision in intersection testing. Many general purpose processors are used to implement ray tracing, and these processors provide full-precision IEEE floating point units, and ray tracing software can benefit from this built-in floating point capability.
Using fixed point math in ray tracing also has been considered. Fixed integer math used in ray tracing generally calls for sub-dividing an extent of a scene into equally sized subdivisions of a size that depends on an available number of bits in the integer format being used, and a size of the scene being rendered. Then, positions of objects in the scene and ray data are quantized to a nearest number representable within the number of bits provided. Fixed point arithmetic allows for a much smaller range of representable numbers than floating point arithmetic. Fixed point arithmetic also generally involves an analysis of a particular scene to be rendered, such that the scene can be adapted to fixed point representation in an intelligent way, and generalizing the use of fixed point arithmetic to full-resolution problems and for more arbitrary scenes may be difficult.